package cn.good.yan.sf.t6.priority;


import cn.good.yan.sf.t6.Queue;
import org.omg.CORBA.Object;

import javax.jws.Oneway;

/**
 * 6 优先级队列 - 基于 堆（小顶堆）
 *
 * @author shengren.yan
 * @create 2024-07-22
 */
@SuppressWarnings("all")
public class PriorityQueue5 {

    MergeNode[] arr;
    int size;

    public PriorityQueue5(int num) {
        arr = new MergeNode[num];
    }

    public boolean offer(MergeNode node) {
        if (isFull()) {
            return false;
        }
        int son = size++;
        int fater = (son - 1) / 2;
        while (son > 0 && node.value < arr[fater].value) {
            arr[son] = arr[fater];
            son = fater;
            fater = (son - 1) / 2;
        }
        arr[son] = node;
        return true;
    }

    public MergeNode pool() {
        if (isEmpty()) {
            return null;
        }
        jh(0, size - 1);
        MergeNode node = arr[size - 1];
        arr[size - 1] = null;
        size--;
        // 下潜
        down(0);
        return node;
    }

    private void down(int i) {
        int min = i;
        int left = 2 * i + 1;
        int right = left + 1;
        if (left < size && arr[left].value < arr[min].value) {
            min = left;
        }
        if (right < size && arr[right].value < arr[min].value) {
            min = right;
        }
        if (min != i) {
            jh(i, min);
            down(min);
        }
    }

    private void jh(int i, int j) {
        MergeNode t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public MergeNode peek() {
        if (isEmpty()) {
            return null;
        }
        return arr[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == arr.length;
    }

    public static void main(String[] args) {
        PriorityQueue5 queue = new PriorityQueue5(6);
        // 添加元素
        System.out.println("添加元素：" + queue.offer(new MergeNode(1,null)));
        System.out.println("添加元素：" + queue.offer(new MergeNode(5,null)));
        System.out.println("添加元素：" + queue.offer(new MergeNode(2,null)));
        System.out.println("添加元素：" + queue.offer(new MergeNode(3,null)));
        System.out.println("添加元素：" + queue.offer(new MergeNode(4,null)));
        System.out.println("---------------------------");
        System.out.println("获取头元素：" + queue.peek().value);
        System.out.println("获取头元素：" + queue.peek().value);
        System.out.println("---------------------------");
        System.out.println("移除头元素：" + queue.pool().value);
        System.out.println("移除头元素：" + queue.pool().value);
        System.out.println("移除头元素：" + queue.pool().value);
        System.out.println("移除头元素：" + queue.pool().value);
        System.out.println("移除头元素：" + queue.pool().value);
        System.out.println("移除头元素：" + queue.pool().value);
        System.out.println("移除头元素：" + queue.pool().value);
        // 正序打印

    }

}
